/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 * sources where taken in a desperate act from here
 * http://homepage.cs.uiowa.edu/~hzhang/c231/codes/
 */
package com.john.utils;

/**
 *
 * @author John
 */
import java.util.*;
import java.io.*;

public class LongestPath {

    int n;	    // number of nodes 
    int target;    // destination node
    int minLength;  // the minimal length of each path
    Node[] v;	    //used to store Nodes 
    Edge[] e;	    //used to store Edges
    int[] path;	    //used to store temporary path 
    int length = 0;	    // length of the path 
    int distance = 0;    // distance of the path
    int[] bestPath;	    //used to store temporary path 
    int bestLength = 0;	    // length of the longest path 
    int bestDistance = -1000000;     // distance of the longest path 
    int[] visited;  //used to mark a node as visited if set as 1

    public LongestPath() {
    }

    public LongestPath(String filename) throws IOException {
        //this function read edge distances from a file
        BufferedReader br = new BufferedReader(
                new FileReader(filename));
        String line = br.readLine();
        StringTokenizer st = new StringTokenizer(line);
        //1st token is the # of nodes
        n = Integer.parseInt(st.nextToken());

        //2nd token is the # of edges
        int m = Integer.parseInt(st.nextToken());

        //create storage for Nodes and Edges
        v = new Node[n];
        e = new Edge[m];
        System.out.println(n + " nodes and " + m + " edges.");

        //create Node objects for graph
        //numbering them as 0, 1, 2, ..., n-1
        for (int i = 0; i < n; i++) {
            v[i] = new Node(i);
        }

        int i = 0;
        while ((line = br.readLine()) != null) {
            //check input file
            if (i >= e.length) {
                System.out.println("# of lines is greater than # of edges in G, exit...");
                System.exit(1);
            }

            Edge edge = new Edge(i);
            st = new StringTokenizer(line);

            //first token is the start point
            String start = st.nextToken();
            int sVal = Integer.parseInt(start);
            edge.start = sVal;

            //2nd token is the end point
            String end = st.nextToken();
            int eVal = Integer.parseInt(end);
            edge.end = eVal;

            //3rd token is weight, the same as capacity
            String capacity = st.nextToken();
            edge.capacity = Integer.parseInt(capacity);

            System.out.println(" edge: " + edge.start + " " + edge.end + " " + edge.capacity);

            edge.flow = 0;
            e[i] = edge;
            //map[sVal][eVal] = i;

            //now save edge information in nodes start and end
            v[sVal].fors.add(i);
            v[eVal].backs.add(i);

            i++;
            if (i == m) {
                break;
            }
        }

        visited = new int[v.length];
        path = new int[v.length];
        bestPath = new int[v.length];
    }

    public LongestPath(List<String> grap) throws IOException {
        //this function read edge distances from a file

        StringTokenizer st = new StringTokenizer(grap.get(0));
        //1st token is the # of nodes
        n = Integer.parseInt(st.nextToken());

        //2nd token is the # of edges
        int m = Integer.parseInt(st.nextToken());


        //create storage for Nodes and Edges
        v = new Node[n];
        e = new Edge[m];
        System.out.println(n + " nodes and " + m + " edges.");

        //create Node objects for graph
        //numbering them as 0, 1, 2, ..., n-1
        for (int i = 0; i < n; i++) {
            v[i] = new Node(i);
        }
        int i = 0;
        grap.remove(0);
        for (Iterator<String> it = grap.iterator(); it.hasNext();) {
            String line = it.next();
            //check input file
            if (i >= e.length) {
                System.out.println("# of lines is greater than # of edges in G, exit...");
                System.exit(1);
            }
            Edge edge = new Edge(i);
            st = new StringTokenizer(line);
            //first token is the start point
            String start = st.nextToken();
            int sVal = Integer.parseInt(start);
            edge.start = sVal;
            //2nd token is the end point
            String end = st.nextToken();
            int eVal = Integer.parseInt(end);
            edge.end = eVal;
            //3rd token is weight, the same as capacity
            String capacity = st.nextToken();
            edge.capacity = Integer.parseInt(capacity);
            System.out.println(" edge: " + edge.start + " " + edge.end + " " + edge.capacity);
            edge.flow = 0;
            e[i] = edge;
            //map[sVal][eVal] = i;
            //now save edge information in nodes start and end
            v[sVal].fors.add(i);
            v[eVal].backs.add(i);
            i++;
            if (i == m) {
                break;
            }
        }

        visited = new int[v.length];
        path = new int[v.length];
        bestPath = new int[v.length];
    }

    // this function looks for a longest path starting from being to end, 
    // using the backtrack depth-first search.
    public boolean findLongestPath(int begin, int end, int minLen) {
        // compute a longest path from begin to end
        target = end;
        bestDistance = -100000000;
        minLength = minLen;
        dfsLongestPath(begin);
        if (bestDistance == -100000000) {
            return false;
        } else {
            return true;
        }
    }

    private void dfsLongestPath(int current) {
        visited[current] = 1;
        path[length++] = current;

        if (current == target && length >= minLength) { // a path from source to target is found.
            if (distance > bestDistance) { // if a longer path is found
                for (int i = 0; i < length; i++) {
                    bestPath[i] = path[i];
                }
                bestLength = length;
                bestDistance = distance;
            }
        } else {
            //get current's edges
            Vector<Integer> fors = v[current].fors;

            //select an unvisited forward edge
            for (int i = 0; i < fors.size(); i++) {
                Integer edge_obj = (Integer) fors.elementAt(i);
                int edge = edge_obj.intValue();

                if (visited[e[edge].end] == 0) {//not yet visited
                    distance += e[edge].capacity;
                    dfsLongestPath(e[edge].end);
                    distance -= e[edge].capacity;
                }
            }
        }

        // finish with current and unmark current.
        visited[current] = 0;
        length--;
    }

    public String toString() {
        String output = "" + bestPath[0];
        for (int i = 1; i < bestLength; i++) {
            output = output + "," + bestPath[i];
        }
        return output;
    }

    public static void main(String arg[]) {
        LongestPath lp = new LongestPath();
        try {
            List<String> d = new ArrayList<>();
            d.add("6 7");
            d.add("0 1 4");
            d.add("0 2 3");
            d.add("2 3 3");
            d.add("1 4 1");
            d.add("1 3 1");
            d.add("3 5 3");
            d.add("4 5 3");
            lp = new LongestPath(d);
            // lp = new LongestPath("D:\\John\\graph2.txt");
        } catch (IOException e) {
            System.out.println("Read file error, exit....");
            System.exit(1);
        }

        // find a longest path from vertex 0 to vertex n-1.
        if (lp.findLongestPath(0, lp.n - 1, 1)) {
            System.out.println("Longest Path is " + lp + " and the distance is " + lp.bestDistance);
        } else {
            System.out.println("No path from v0 to v" + (lp.n - 1));
        }

        // find a longest path from vertex 3 to vertex 5.
        if (lp.findLongestPath(3, 5, 1)) {
            System.out.println("Longest Path is " + lp + " and the distance is " + lp.bestDistance);
        } else {
            System.out.println("No path from v3 to v5");
        }

        // find a longest path from vertex 5 to vertex 3.
        if (lp.findLongestPath(lp.n - 1, 3, 1)) {
            System.out.println("Longest Path is " + lp + " and the distance is " + lp.bestDistance);
        } else {
            System.out.println("No path from v5 to v3");
        }

    }

    //===============0
    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }

    public int getTarget() {
        return target;
    }

    public void setTarget(int target) {
        this.target = target;
    }

    public int getMinLength() {
        return minLength;
    }

    public void setMinLength(int minLength) {
        this.minLength = minLength;
    }

    public Node[] getV() {
        return v;
    }

    public void setV(Node[] v) {
        this.v = v;
    }

    public Edge[] getE() {
        return e;
    }

    public void setE(Edge[] e) {
        this.e = e;
    }

    public int[] getPath() {
        return path;
    }

    public void setPath(int[] path) {
        this.path = path;
    }

    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }

    public int getDistance() {
        return distance;
    }

    public void setDistance(int distance) {
        this.distance = distance;
    }

    public int[] getBestPath() {
        return bestPath;
    }

    public void setBestPath(int[] bestPath) {
        this.bestPath = bestPath;
    }

    public int getBestLength() {
        return bestLength;
    }

    public void setBestLength(int bestLength) {
        this.bestLength = bestLength;
    }

    public int getBestDistance() {
        return bestDistance;
    }

    public void setBestDistance(int bestDistance) {
        this.bestDistance = bestDistance;
    }

    public int[] getVisited() {
        return visited;
    }

    public void setVisited(int[] visited) {
        this.visited = visited;
    }
    
}
